package com.bigshen.algorithm.gTree.solution01SerializableDes;

import java.util.ArrayList;
import java.util.List;

public class Solution {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (null == root) {
            return "[]";
        }
        List<TreeNode> list = new ArrayList();
        list.add(root);
        for (int i = 0; i < list.size(); i++) {
            TreeNode node = list.get(i);
            if (null == node) {
                continue;
            }
            list.add(node.left);
            list.add(node.right);
        }
        while (list.get(list.size()-1) == null) {
            list.remove(list.size()-1);
        }
        StringBuffer sb = new StringBuffer("[");
        sb.append(list.get(0).val);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) == null) {
                sb.append(",#");
            } else {
                sb.append("," + list.get(i).val);
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (null == data || data.equals("[]")) {
            return null;
        }
        data = data.replace("[", "").replace("]", "");
        String[] array = data.split(",");

        List<TreeNode> nodeList = new ArrayList();
        TreeNode root = new TreeNode(Integer.parseInt(array[0]));
        nodeList.add(root);
        int index = 0;
        // 从左子节点开始
        boolean isRight = false;

        for (int i = 1; i < array.length; i ++) {
            String element = array[i];
            if (!element.equals("#")) {
                TreeNode parent = nodeList.get(index);
                TreeNode current = new TreeNode(Integer.parseInt(element));
                if (isRight) {
                    parent.right = current;
                } else {
                    parent.left = current;
                }
                nodeList.add(current);
            }
            // 添加完右节点，父节点切换
            if (isRight) {
                index++;
            }
            isRight = !isRight;
        }
        return root;
    }


    public static void main(String[] args) {

        Solution solution = new Solution();
        TreeNode node = solution.deserialize("[1,2,3,#,#,4,5,6,7]");

        System.out.println(node);

        System.out.println(solution.serialize(node));

    }

}
